package arithmetic;

/**
 * @Author: Jie
 * @Date: 2019/3/11 15:29
 * @Function : 52 N Queens 的数量
 */
public class A_23_NQueens {
    public static void main(String[] args) {
        int count = totalNQueens(4);
        System.out.println(count);
    }

    private static int count;//记录结果。
    public static int totalNQueens(int n) {
        if (n < 1)
            return 0;
        dfsbit(n,0,0,0,0);
        return count;
    }

    /**
     * //用二进制表示 棋盘矩阵。1表示皇后。
     * //pie na 不用set 用int 表示
     * @param n 仅仅，表示，n这个最大值。
     * @param row 仅仅，表示，递归的深度。因为每 1 row 都是新的深度，都可以选。
     * @param col 表示，哪些列已经有皇后的位置。eg: 0010 ,表示，第三列有皇后了。
     * @param pie 表示，当前行。pie，哪些位置已经有了皇后。
     *            eg: n = 4 当
     *            第一行 0100 ，为Q时。
     *            第二行 1000 ，这个位置不能有值。斜线不能有值。就等于 0100 << 1 位。正好45°。
     *
     * @param na  表示，当前行。na，哪些位置已经有了皇后。
     *            eg: n = 4 当
     *            第一行 0100 ，为Q时。
     *            第二行 0010 ，这个位置不能有值。斜线不能有值。就等于 0100 >> 1 位。正好45°。
     */
    private static void dfsbit(int n, int row, int col, int pie, int na) {
        //终止条件
        if (row >= n){//深度超过了矩阵，表示 有解
            count++;
            return;
        }
        //bit:当前可以放皇后的位置,用【1】表示 ，eg bits: 0010 1001
        // ~(col | pie | na) ，取反，得到可以放皇后的位置。
        //     当前 col 现在有皇后的位置。
        //     pie na 现在有皇后的位置。
        //     (col | pie | na) 现在所有不能放皇后的位置。
        // ((1<<n) -1) 一个筛子。& 前面的值，去调高位的1。
        //     ((1<<n) -1))的作用去掉前面的干扰的1，eg: 0111111111 0111 0111
        //     (1<<n) -1 的解释： 获得低位n个1 eg: n = 8 ,那就是 00000 1111 1111，
        //     1左移 8位。 1 0000 0000 ，-1等于 0000 1111 1111.
        int bits = (~(col | pie | na) & ((1<<n) -1));

        //遍历每一个 【1】可以放置 Q 的位置，枚举完所有的可能。 eg: 1000 1000
        while (bits > 0){//直到 bits == 0

            //p: while 依次拿到，就是可以放 皇后的位置, 最低位的 【1】,eg bits = 10010,p= 10
            //  解释：eg -bits 先取反，再+1
            //      bits= 10100
            //      取反 = 01011
            //      +1 =  01100
            //      结果  00100 。拿到最低位的1，高位都相反所以忽略。
            int p = bits & -bits;

            //更新 col pie na eg:
            //    col | p   ,pie | p 表示 这 1 行加的限制。。这个位置有 1 了。不能再放 1 了。
            //    pie = 0001   << 1 表示 下一行的限制位置。下一行就变成了，向左移了 1 位。 na 相同。
            //    pie = 0010
            dfsbit(n,row+1,col|p , (pie | p)<<1,(na | p)>>1);

            //去掉 p，已经尝试的 1.最低位的 【1】
                //解释 bits & (bits -1)
                //bits   1010100
                //bits-1 1010011
                //结果：  1010000。
            bits = bits & (bits -1);
        }
    }
}
